{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Flip Binary Tree To Match Preorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: flipMatchVoyage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转二叉树以匹配先序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，树中有 <code>n</code> 个节点，每个节点都有一个不同于其他节点且处于 <code>1</code> 到 <code>n</code> 之间的值。</p>\n",
    "\n",
    "<p>另给你一个由 <code>n</code> 个值组成的行程序列 <code>voyage</code> ，表示 <strong>预期</strong> 的二叉树 <a href=\"https://baike.baidu.com/item/%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86/6442839?fr=aladdin\" target=\"_blank\"><strong>先序遍历</strong></a> 结果。</p>\n",
    "\n",
    "<p>通过交换节点的左右子树，可以 <strong>翻转</strong> 该二叉树中的任意节点。例，翻转节点 1 的效果如下：</p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/15/fliptree.jpg\" style=\"width: 400px; height: 187px;\" />\n",
    "<p>请翻转 <strong>最少 </strong>的树中节点，使二叉树的 <strong>先序遍历</strong> 与预期的遍历行程 <code>voyage</code> <strong>相匹配</strong> 。 </p>\n",
    "\n",
    "<p>如果可以，则返回 <strong>翻转的</strong> 所有节点的值的列表。你可以按任何顺序返回答案。如果不能，则返回列表 <code>[-1]</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/02/1219-01.png\" style=\"width: 150px; height: 205px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2], voyage = [2,1]\n",
    "<strong>输出：</strong>[-1]\n",
    "<strong>解释：</strong>翻转节点无法令先序遍历匹配预期行程。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/02/1219-02.png\" style=\"width: 150px; height: 142px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3], voyage = [1,3,2]\n",
    "<strong>输出：</strong>[1]\n",
    "<strong>解释：</strong>交换节点 2 和 3 来翻转节点 1 ，先序遍历可以匹配预期行程。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/01/02/1219-02.png\" style=\"width: 150px; height: 142px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,2,3], voyage = [1,2,3]\n",
    "<strong>输出：</strong>[]\n",
    "<strong>解释：</strong>先序遍历已经匹配预期行程，所以不需要翻转节点。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数目为 <code>n</code></li>\n",
    "\t<li><code>n == voyage.length</code></li>\n",
    "\t<li><code>1 <= n <= 100</code></li>\n",
    "\t<li><code>1 <= Node.val, voyage[i] <= n</code></li>\n",
    "\t<li>树中的所有值 <strong>互不相同</strong></li>\n",
    "\t<li><code>voyage</code> 中的所有值 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [flip-binary-tree-to-match-preorder-traversal](https://leetcode.cn/problems/flip-binary-tree-to-match-preorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [flip-binary-tree-to-match-preorder-traversal](https://leetcode.cn/problems/flip-binary-tree-to-match-preorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2]\\n[2,1]', '[1,2,3]\\n[1,3,2]', '[1,2,3]\\n[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: TreeNode, vy: List[int]) -> List[int]:\n",
    "        if not root: return []\n",
    "        if root.right == root.left == None: return []\n",
    "        result = []\n",
    "        flag = True\n",
    "\n",
    "        def dfs(rt):\n",
    "            nonlocal result, flag,  vy\n",
    "            if vy == []: return\n",
    "            if rt.val != vy[0]:\n",
    "                flag = False\n",
    "                return\n",
    "            if len(vy) == 1: return\n",
    "            if rt.left != None:\n",
    "                if rt.left.val != vy[1] and rt.right != None and rt.right.val == vy[1]:\n",
    "                    rt.left, rt.right = rt.right, rt.left\n",
    "                    result.append(rt.val)\n",
    "                vy = vy[1:]\n",
    "                dfs(rt.left)\n",
    "            if rt.right != None:\n",
    "                vy = vy[1:]\n",
    "                dfs(rt.right)\n",
    "        dfs(root)\n",
    "        if not flag: return [-1]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:\n",
    "        def dfs(node):\n",
    "            nonlocal idx\n",
    "            if not node:\n",
    "                return True\n",
    "            if node.val != voyage[idx]:\n",
    "                return False\n",
    "            idx += 1\n",
    "            if node.left and node.left.val != voyage[idx]:\n",
    "                node.left, node.right = node.right, node.left\n",
    "                result.append(node.val)\n",
    "            return dfs(node.left) and dfs(node.right)\n",
    "        idx, result = 0, []\n",
    "        return result if dfs(root) else [-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1\n",
    "                return ret\n",
    "            if root.val == voyage[i]:\n",
    "                i += 1\n",
    "                if root.left and root.right:\n",
    "                    if root.right.val == voyage[i]:\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                elif root.left:\n",
    "                    return dfs(root.left)\n",
    "                else:\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    return \n",
    "                self.i += 1\n",
    "\n",
    "                if (self.i<len(voyage)) and node.left and node.left.val != voyage[self.i]:\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.i = 0\n",
    "        self.false = True\n",
    "\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.traverse(root, voyage)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root, voyage):\n",
    "        if not root:\n",
    "            return\n",
    "        if -1 in self.res:\n",
    "            return\n",
    "        if root.val != voyage[self.i]:\n",
    "            self.res.clear()\n",
    "            self.res.append(-1)\n",
    "            return\n",
    "        self.i += 1\n",
    "        if root.left and root.left.val != voyage[self.i]:\n",
    "            self.res.append(root.val)\n",
    "            root.left, root.right = root.right, root.left\n",
    "        self.traverse(root.left, voyage)\n",
    "        self.traverse(root.right, voyage)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def flipMatchVoyage(self, root, voyage):\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    return\n",
    "                self.i += 1\n",
    "\n",
    "                if (self.i < len(voyage) and\n",
    "                        node.left and node.left.val != voyage[self.i]):\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1\n",
    "                return ret\n",
    "            if root.val == voyage[i]:\n",
    "                i += 1\n",
    "                if root.left and root.right:\n",
    "                    if root.right.val == voyage[i]:\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                elif root.left:\n",
    "                    return dfs(root.left)\n",
    "                else:\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.idx = 0\n",
    "\n",
    "        def traverse(root):\n",
    "            if not root or self.idx == len(voyage):\n",
    "                return\n",
    "            if root.val != voyage[self.idx]:\n",
    "                self.flipped = [-1]\n",
    "                return\n",
    "\n",
    "            self.idx += 1\n",
    "            if root.left and root.left.val != voyage[self.idx]:\n",
    "                self.flipped.append(root.val)\n",
    "                traverse(root.right)\n",
    "                traverse(root.left)\n",
    "            else:\n",
    "                traverse(root.left)\n",
    "                traverse(root.right)\n",
    "\n",
    "        traverse(root)\n",
    "        return [-1] if self.flipped and self.flipped[0] == -1 else self.flipped\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.idx = 0\n",
    "\n",
    "        def traverse(root):\n",
    "            if root:\n",
    "                if self.idx == len(voyage):\n",
    "                    return\n",
    "                if root.val != voyage[self.idx]:\n",
    "                    self.flipped = [-1]\n",
    "                    return\n",
    "\n",
    "                self.idx += 1\n",
    "                if root.left and root.left.val != voyage[self.idx]:\n",
    "                    self.flipped.append(root.val)\n",
    "                    traverse(root.right)\n",
    "                    traverse(root.left)\n",
    "                else:\n",
    "                    traverse(root.left)\n",
    "                    traverse(root.right)\n",
    "\n",
    "        traverse(root)\n",
    "        return [-1] if self.flipped and self.flipped[0] == -1 else self.flipped\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        self.lst = []\n",
    "        def dfs(root):\n",
    "            nonlocal i\n",
    "            if not root: return None\n",
    "            if root.val != voyage[i]:\n",
    "                self.lst= [-1]\n",
    "                return\n",
    "            i += 1\n",
    "            if (i < len(voyage)) and root.left and root.left.val != voyage[i]:\n",
    "                self.lst.append(root.val)\n",
    "                dfs(root.right)\n",
    "                dfs(root.left)\n",
    "            else:       \n",
    "                dfs(root.left)\n",
    "                dfs(root.right)\n",
    "        dfs(root)\n",
    "        if self.lst and self.lst[0] == -1:\n",
    "            self.lst = [-1]\n",
    "        return self.lst\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    return \n",
    "                self.i += 1\n",
    "                if (self.i < len(voyage) and node.left and node.left.val != voyage[self.i]):\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "        dfs(root)\n",
    "\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "\n",
    "        return self.flipped"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1\n",
    "                return ret\n",
    "            if root.val == voyage[i]:\n",
    "                i += 1\n",
    "                if root.left and root.right:\n",
    "                    if root.right.val == voyage[i]:\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                elif root.left:\n",
    "                    return dfs(root.left)\n",
    "                else:\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1\n",
    "                return ret\n",
    "            if root.val == voyage[i]:\n",
    "                i += 1\n",
    "                if root.left and root.right:\n",
    "                    if root.right.val == voyage[i]:\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                elif root.left:\n",
    "                    return dfs(root.left)\n",
    "                else:\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node: Optional[TreeNode]):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    return\n",
    "                self.i += 1\n",
    "                if (\n",
    "                    self.i < len(voyage)\n",
    "                    and node.left\n",
    "                    and node.left.val != voyage[self.i]\n",
    "                ):\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n=0\n",
    "res=[]\n",
    "def go_next(node:Optional[TreeNode],voyage: List[int]):\n",
    "    global n\n",
    "    global res\n",
    "    flag=0\n",
    "    if node.left is not None and node.right is not None:\n",
    "        flag=0\n",
    "    if node.left is not None and node.right is None:\n",
    "        flag=1\n",
    "    if node.right is not None and node.left is None:\n",
    "        flag=2\n",
    "    if node.left is None and node.right is None:\n",
    "        flag=4\n",
    "    if flag==4:\n",
    "        return -2\n",
    "    if flag==1:\n",
    "        if node.left.val!=voyage[n]:\n",
    "            return -1\n",
    "        else:\n",
    "            n+=1\n",
    "            ans=go_next(node.left,voyage)\n",
    "            if ans==-1:\n",
    "                return -1\n",
    "    if flag==2:\n",
    "        if node.right.val!=voyage[n]:\n",
    "            return -1\n",
    "        else:\n",
    "            n+=1\n",
    "            ans=go_next(node.right,voyage)\n",
    "            if ans==-1:\n",
    "                return -1\n",
    "    if flag==0:\n",
    "        if node.left.val==voyage[n]:\n",
    "            n+=1\n",
    "            ans=go_next(node.left,voyage)\n",
    "            if ans==-1:\n",
    "                return -1\n",
    "            if node.right.val==voyage[n]:\n",
    "                n+=1\n",
    "                ans=go_next(node.right,voyage)\n",
    "                if ans==-1:\n",
    "                    return -1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        else:\n",
    "            if node.right.val==voyage[n]:\n",
    "                res.append(voyage[n-1])\n",
    "                n+=1\n",
    "                ans=go_next(node.right,voyage)\n",
    "                if ans==-1:\n",
    "                    return -1\n",
    "                if node.left.val == voyage[n]:\n",
    "                    n += 1\n",
    "                    ans = go_next(node.left, voyage)\n",
    "                    if ans == -1:\n",
    "                        return -1\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                return -1\n",
    "    return 1\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "\n",
    "        global n\n",
    "        global res\n",
    "        n=0\n",
    "        res=[]\n",
    "        if root.val!=voyage[0]:\n",
    "            return [-1]\n",
    "        else:\n",
    "            n=1\n",
    "            ans=go_next(root,voyage)\n",
    "            if ans==-1:\n",
    "                return [-1]\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        r = []\n",
    "        if root is None:\n",
    "            return []\n",
    "        if self.inner_file(root, voyage, r):\n",
    "            return r\n",
    "        else:\n",
    "            return [-1]\n",
    "\n",
    "    def inner_file(self, root, voyage, result):\n",
    "        if len(voyage) == 0 or root.val != voyage[0]:\n",
    "            return False\n",
    "        min_num = 1\n",
    "        if root.left:\n",
    "            min_num += 1\n",
    "        if root.right:\n",
    "            min_num += 1\n",
    "        if len(voyage) < min_num:\n",
    "            return False\n",
    "        if root.left:\n",
    "            if root.left.val == voyage[1]:\n",
    "                if not root.right:\n",
    "                    return self.inner_file(root.left, voyage[1:], result)\n",
    "                else:\n",
    "                        \n",
    "                    right_index = -1\n",
    "                    for i in range(1, len(voyage)):\n",
    "                        if voyage[i] == root.right.val:\n",
    "                            right_index = i\n",
    "                            break\n",
    "                    if right_index == -1:\n",
    "                        return False\n",
    "                    return self.inner_file(root.left, voyage[1:right_index],result) and self.inner_file(root.right, voyage[right_index:], result)\n",
    "            else:\n",
    "                if not root.right:\n",
    "                    return False\n",
    "                if root.right.val == voyage[1]:\n",
    "                    left_index = -1\n",
    "                    for i in range(1, len(voyage)):\n",
    "                        if voyage[i] == root.left.val:\n",
    "                            left_index = i\n",
    "                            break\n",
    "                    if left_index == -1:\n",
    "                        return False\n",
    "                    result.append(root.val)\n",
    "                    return self.inner_file(root.right, voyage[1:left_index], result) and self.inner_file(root.left, voyage[left_index:], result)\n",
    "        else:\n",
    "            if root.right:\n",
    "                return self.inner_file(root.right, voyage[1:], result)\n",
    "            else:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.traverse(root, voyage)\n",
    "        return self.res\n",
    "\n",
    "    def traverse(self, root, voyage):\n",
    "        if not root:\n",
    "            return\n",
    "        if -1 in self.res:\n",
    "            return\n",
    "        value = voyage.pop(0)\n",
    "        if root.val != value:\n",
    "            self.res.clear()\n",
    "            self.res.append(-1)\n",
    "            return\n",
    "        if root.left and root.left.val != voyage[0]:\n",
    "            self.res.append(root.val)\n",
    "            root.left, root.right = root.right, root.left\n",
    "        self.traverse(root.left, voyage)\n",
    "        self.traverse(root.right, voyage)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.index = 0\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        answer_list = list()\n",
    "        voyage_length = len(voyage)\n",
    "        if self.preOrderTraverse(root, answer_list, voyage):\n",
    "            return answer_list\n",
    "        else:\n",
    "            return [-1]\n",
    "\n",
    "    def preOrderTraverse(self, root, answer_list, voyage):\n",
    "        if root == None:\n",
    "            return True\n",
    "\n",
    "        if root.val != voyage[self.index]:\n",
    "            return False \n",
    "\n",
    "        if root.left and root.left.val != voyage[self.index + 1]:\n",
    "            temp = root.left \n",
    "            root.left = root.right \n",
    "            root.right = temp \n",
    "            answer_list.append(root.val)\n",
    "        self.index += 1\n",
    "        if self.preOrderTraverse(root.left, answer_list, voyage):\n",
    "            return self.preOrderTraverse(root.right, answer_list, voyage)\n",
    "        else:\n",
    "            return False \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        res=[]\n",
    "        index=0\n",
    "        queue=[root]\n",
    "        while queue:\n",
    "            p=queue.pop()\n",
    "            if not p:\n",
    "                continue\n",
    "            if p.val!=voyage[index] or index>len(voyage)-1:\n",
    "                res.append(-1)\n",
    "                break\n",
    "            index+=1\n",
    "            if p.left and p.left.val!=voyage[index]:\n",
    "                res.append(p.val)\n",
    "                queue.append(p.left)\n",
    "                queue.append(p.right)\n",
    "            else:\n",
    "                queue.append(p.right)\n",
    "                queue.append(p.left)\n",
    "        if not res:\n",
    "            return []\n",
    "        if -1 not in res:\n",
    "            return res\n",
    "        else:\n",
    "            return [-1]\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: # py3\n",
    "    def __init__(self):\n",
    "        self.i = 0\n",
    "        self.can = True\n",
    "        self.ans = []\n",
    "    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:\n",
    "        def dfs(root, voyage):\n",
    "            if not self.can or not root:\n",
    "                return\n",
    "            if root.val == voyage[self.i]:\n",
    "                self.i += 1\n",
    "                if root.left and root.left.val == voyage[self.i]:\n",
    "                    dfs(root.left,voyage)\n",
    "                    dfs(root.right, voyage)\n",
    "                elif root.right and root.right.val == voyage[self.i]:\n",
    "                    if root.left:\n",
    "                        self.ans.append(root.val)\n",
    "                    dfs(root.right, voyage)\n",
    "                    dfs(root.left, voyage)\n",
    "                elif root.left or root.right:\n",
    "                    self.can = False\n",
    "            else:\n",
    "                self.can = False\n",
    "        dfs(root, voyage)\n",
    "        if not self.can:\n",
    "            return [-1]\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        stk = []\n",
    "        node = root\n",
    "        while stk or node:\n",
    "            if not node:\n",
    "                node = stk.pop()\n",
    "                node = node.right\n",
    "                continue\n",
    "            if node.val != voyage[i]:\n",
    "                return [-1]\n",
    "            stk.append(node)\n",
    "            i += 1\n",
    "            if i < len(voyage) and node.left and node.left.val != voyage[i]:\n",
    "                ans.append(node.val)\n",
    "                node.left, node.right = node.right, node.left\n",
    "            node = node.left\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:    \n",
    "        ans = []\n",
    "        i = 0\n",
    "        s = [root]\n",
    "        while s:\n",
    "            node = s.pop()\n",
    "            if not node: continue\n",
    "            print(f\"node:{node.val}, i:{i}\")\n",
    "            if node.val != voyage[i]: return [-1]\n",
    "            i+=1\n",
    "            if node.left and node.left.val == voyage[i]:\n",
    "                s.append(node.right)\n",
    "                s.append(node.left)\n",
    "            elif node.right and node.right.val == voyage[i]:\n",
    "                if node.left:\n",
    "                    ans.append(node.val)\n",
    "                s.append(node.left)\n",
    "                s.append(node.right)\n",
    "            elif node.left or node.right:\n",
    "                return [-1]\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.i = 0\n",
    "        self.canFlip = True\n",
    "\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.voyage = voyage\n",
    "        self.traverse(root)\n",
    "        if self.canFlip:\n",
    "            return self.res\n",
    "        return [-1]\n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root == None or self.canFlip != True:\n",
    "            return \n",
    "        if root.val != self.voyage[self.i]:\n",
    "            self.canFlip = False\n",
    "            return\n",
    "        self.i += 1\n",
    "        if root.left != None and root.left.val != self.voyage[self.i]:\n",
    "            temp = root.left\n",
    "            root.left = root.right\n",
    "            root.right = temp\n",
    "            self.res.append(root.val)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    # 注意这里的return只会结束当前递归层的函数，如果父层函数没有执行完毕则还会继续执行，\n",
    "                    # 可以解释下面没有最后的if 判断会出现[-1, x]的输出结果。\n",
    "                    return \n",
    "                self.i += 1\n",
    "\n",
    "                if (self.i<len(voyage)) and node.left and node.left.val != voyage[self.i]:\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        # 下面的两句话十分重要，没有则会导致[-1, x]的输出，并不是我们想要的\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.res = []\n",
    "\n",
    "        self.voyage = voyage\n",
    "        self.traverse(root)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None or -1 in self.res:\n",
    "            return \n",
    "\n",
    "        cur = self.voyage.pop(0)\n",
    "        if root.val != cur:\n",
    "            self.res = [-1]\n",
    "            return \n",
    "\n",
    "        if root.left and root.left.val != self.voyage[0]:\n",
    "            root.left, root.right = root.right, root.left \n",
    "            self.res.append(root.val)\n",
    "\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "n=0\n",
    "res=[]\n",
    "def go_next(node:Optional[TreeNode],voyage: List[int]):\n",
    "    global n\n",
    "    global res\n",
    "    flag=0\n",
    "    if node.left is not None and node.right is not None:\n",
    "        flag=0\n",
    "    if node.left is not None and node.right is None:\n",
    "        flag=1\n",
    "    if node.right is not None and node.left is None:\n",
    "        flag=2\n",
    "    if node.left is None and node.right is None:\n",
    "        flag=4\n",
    "    if flag==4:\n",
    "        return -2\n",
    "    if flag==1:\n",
    "        if node.left.val!=voyage[n]:\n",
    "            return -1\n",
    "        else:\n",
    "            n+=1\n",
    "            ans=go_next(node.left,voyage)\n",
    "            if ans==-1:\n",
    "                return -1\n",
    "    if flag==2:\n",
    "        if node.right.val!=voyage[n]:\n",
    "            return -1\n",
    "        else:\n",
    "            n+=1\n",
    "            ans=go_next(node.right,voyage)\n",
    "            if ans==-1:\n",
    "                return -1\n",
    "    if flag==0:\n",
    "        if node.left.val==voyage[n]:\n",
    "            n+=1\n",
    "            ans=go_next(node.left,voyage)\n",
    "            if ans==-1:\n",
    "                return -1\n",
    "            if node.right.val==voyage[n]:\n",
    "                n+=1\n",
    "                ans=go_next(node.right,voyage)\n",
    "                if ans==-1:\n",
    "                    return -1\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        else:\n",
    "            if node.right.val==voyage[n]:\n",
    "                res.append(voyage[n-1])\n",
    "                n+=1\n",
    "                ans=go_next(node.right,voyage)\n",
    "                if ans==-1:\n",
    "                    return -1\n",
    "                if node.left.val == voyage[n]:\n",
    "                    n += 1\n",
    "                    ans = go_next(node.left, voyage)\n",
    "                    if ans == -1:\n",
    "                        return -1\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                return -1\n",
    "    return 1\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "\n",
    "        global n\n",
    "        global res\n",
    "        n=0\n",
    "        res=[]\n",
    "        if root.val!=voyage[0]:\n",
    "            return [-1]\n",
    "        else:\n",
    "            n=1\n",
    "            ans=go_next(root,voyage)\n",
    "            if ans==-1:\n",
    "                return [-1]\n",
    "            else:\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.res = []\n",
    "\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        cur = voyage.pop(0)\n",
    "        if cur != root.val:\n",
    "            return [-1]\n",
    "\n",
    "        res = []\n",
    "        if root.left and root.left.val != voyage[0]:\n",
    "            res.append(root.val)\n",
    "            root.left, root.right = root.right, root.left \n",
    "\n",
    "        res.extend(self.flipMatchVoyage(root.left, voyage))\n",
    "        res.extend(self.flipMatchVoyage(root.right, voyage))\n",
    "\n",
    "        return res if -1 not in res else [-1]\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution: # py3\n",
    "    def __init__(self):\n",
    "        self.i = 0\n",
    "        self.can = True\n",
    "        self.ans = []\n",
    "    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:\n",
    "        def dfs(root, voyage):\n",
    "            if not self.can or not root:\n",
    "                return\n",
    "            if root.val == voyage[self.i]:\n",
    "                self.i += 1\n",
    "                if root.left and root.left.val == voyage[self.i]:\n",
    "                    dfs(root.left,voyage)\n",
    "                    dfs(root.right, voyage)\n",
    "                elif root.right and root.right.val == voyage[self.i]:\n",
    "                    if root.left:\n",
    "                        self.ans.append(root.val)\n",
    "                    dfs(root.right, voyage)\n",
    "                    dfs(root.left, voyage)\n",
    "                elif root.left or root.right:\n",
    "                    self.can = False\n",
    "            else:\n",
    "                self.can = False\n",
    "        dfs(root, voyage)\n",
    "        if not self.can:\n",
    "            return [-1]\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    return \n",
    "                self.i += 1\n",
    "\n",
    "                if (self.i<len(voyage)) and node.left and node.left.val != voyage[self.i]:\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.idx = 0\n",
    "\n",
    "        def traverse(root):\n",
    "            if not root or self.idx == len(voyage):\n",
    "                return\n",
    "            if root.val != voyage[self.idx]:\n",
    "                self.flipped = [-1]\n",
    "                return\n",
    "\n",
    "            self.idx += 1\n",
    "            if root.left and root.left.val != voyage[self.idx]:\n",
    "                self.flipped.append(root.val)\n",
    "                traverse(root.right)\n",
    "                traverse(root.left)\n",
    "            else:\n",
    "                traverse(root.left)\n",
    "                traverse(root.right)\n",
    "\n",
    "        traverse(root)\n",
    "        return [-1] if self.flipped and self.flipped[0] == -1 else self.flipped\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        # 这个翻转本质上就是先遍历左边还是右边\n",
    "        ans = []\n",
    "        n = len(voyage)\n",
    "        stack = [root]\n",
    "        i = 0\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur is None:\n",
    "                continue\n",
    "            if cur.val != voyage[i]:\n",
    "                return [-1]\n",
    "            if cur.left is None or cur.left.val != voyage[i + 1]:\n",
    "                if cur.right is not None and cur.left is not None:  # 如果出现一个None，那么交换是无意义的\n",
    "                    ans.append(cur.val)\n",
    "                stack.append(cur.left)\n",
    "                stack.append(cur.right)\n",
    "            else:\n",
    "                stack.append(cur.right)\n",
    "                stack.append(cur.left)\n",
    "            i += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:\n",
    "        # 先序遍历时，若当前节点与对应的voyage数组中的元素值不相同，那么无法匹配，将res数组赋值为[-1]\n",
    "        # 若当前节点与对应的voyage数组中的元素值相同，那么检查当前节点的左节点，若左节点可以与voyage的下一个值匹配，则直接进入下一层遍历\n",
    "        # 若左节点与voyage的下一个值不匹配，那么交换左右节点，把即将交换的节点值压入最后要返回的res数组中，进入下一层遍历（也可直接把右节点传入先序遍历函数中进行遍历，省去一次交换的时间）\n",
    "        res = []\n",
    "        i = 0\n",
    "        def f(node):\n",
    "            nonlocal res, i\n",
    "            if node:\n",
    "                if node.val != voyage[i]:\n",
    "                    res = [-1]\n",
    "                    return \n",
    "                i += 1\n",
    "                if node.left and node.left.val != voyage[i]:\n",
    "                    res.append(node.val)\n",
    "                    f(node.right)\n",
    "                    f(node.left)\n",
    "                else:\n",
    "                    f(node.left)\n",
    "                    f(node.right)\n",
    "            \n",
    "        f(root)\n",
    "        print(res)\n",
    "        return [-1] if res and res[0] == -1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        if root.val != voyage.pop(0):\n",
    "            return [-1]\n",
    "\n",
    "        res = []\n",
    "        if root.left and root.left.val != voyage[0]:\n",
    "            root.left, root.right = root.right, root.left\n",
    "            res.append(root.val)\n",
    "\n",
    "        res.extend(self.flipMatchVoyage(root.left, voyage))\n",
    "        res.extend(self.flipMatchVoyage(root.right, voyage))\n",
    "\n",
    "        return res if -1 not in res else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        # 数组匹配下标\n",
    "        self.i = 0\n",
    "        flipped = []\n",
    "        \n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return True\n",
    "            # 该结点的值不匹配，直接返回false\n",
    "            if node.val != voyage[self.i]:\n",
    "                return False\n",
    "            self.i += 1\n",
    "            # 如果有左孩子，判断中序下一个值是否匹配，不匹配就调换顺序\n",
    "            if node.left and node.left.val != voyage[self.i]:\n",
    "                flipped.append(node.val)\n",
    "                node.left, node.right = node.right, node.left\n",
    "\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            return left and right\n",
    "        if dfs(root):\n",
    "            return flipped\n",
    "        return [-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node: \n",
    "                return True \n",
    "            # value is different\n",
    "            if node.val != voyage[self.i]: \n",
    "                return False \n",
    "\n",
    "            self.i += 1  # increment i\n",
    "\n",
    "            # flip the node\n",
    "            if self.i < len(voyage) and node.left and node.left.val != voyage[self.i]:   \n",
    "                ans.append(node.val)\n",
    "                return dfs(node.right) and dfs(node.left)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "        \n",
    "        ans = []\n",
    "        self.i = 0 # track current node in the `voyage` list\n",
    "        if dfs(root):  # Start a DFS from the root of the tree.\n",
    "            return ans\n",
    "        else:\n",
    "            return [-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "\n",
    "        cur = voyage.pop(0)\n",
    "        if root.val != cur:\n",
    "            return [-1]\n",
    "\n",
    "        res = []\n",
    "        if root.left and root.left.val != voyage[0]:\n",
    "            root.left, root.right = root.right, root.left \n",
    "            res.append(root.val)\n",
    "        \n",
    "        res.extend(self.flipMatchVoyage(root.left, voyage))\n",
    "        res.extend(self.flipMatchVoyage(root.right, voyage))\n",
    "\n",
    "        return res if -1 not in res else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    # 注意这里的return只会结束当前递归层的函数，如果父层函数没有执行完毕则还会继续执行，\n",
    "                    # 可以解释下面没有最后的if 判断会出现[-1, x]的输出结果。\n",
    "                    return \n",
    "                self.i += 1\n",
    "\n",
    "                if (self.i<len(voyage)) and node.left and node.left.val != voyage[self.i]:\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        # 下面的两句话十分重要，没有则会导致[-1, x]的输出，并不是我们想要的\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res: List = list()\n",
    "        self.i = 0\n",
    "        self.voyage: List = list()\n",
    "        self.canFlip = True\n",
    "    def dfs(self, root: Optional[TreeNode]):\n",
    "        if not root or not self.canFlip:\n",
    "            return\n",
    "        if root.val != self.voyage[self.i]:\n",
    "            self.canFlip = False\n",
    "            return\n",
    "        self.i += 1\n",
    "        if root.left and root.left.val != self.voyage[self.i]:\n",
    "            temp = root.left\n",
    "            root.left = root.right\n",
    "            root.right = temp\n",
    "            self.res.append(root.val)\n",
    "        self.dfs(root.left)\n",
    "        self.dfs(root.right)\n",
    "        return\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.voyage = voyage\n",
    "        # 遍历的过程中尝试进行反转\n",
    "        self.dfs(root)\n",
    "        if self.canFlip:\n",
    "            return self.res\n",
    "        return [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        i = 0\n",
    "        def dfs(node):\n",
    "            nonlocal i\n",
    "            if node:\n",
    "                if node.val == voyage[i]:\n",
    "                    i += 1\n",
    "                    if node.left and node.left.val != voyage[i]:\n",
    "                        dfs(node.right)\n",
    "                        dfs(node.left)\n",
    "                        res.append(node.val)\n",
    "                    else:\n",
    "                        dfs(node.left)\n",
    "                        dfs(node.right)\n",
    "\n",
    "                else:\n",
    "                    res.append(-1)\n",
    "                    return\n",
    "\n",
    "\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        return [-1] if -1 in res else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        pos, ans = {val: i for i, val in enumerate(voyage)}, []\n",
    "        def dfs(st, ed, node):\n",
    "            idx = pos[node.val]\n",
    "            if idx != st: return False\n",
    "            if not node.left and not node.right:\n",
    "                if st == ed: return True\n",
    "                return False\n",
    "            elif st == ed: return False\n",
    "            elif not node.left:\n",
    "                if not dfs(st + 1, ed, node.right): return False\n",
    "                return True\n",
    "            elif not node.right:\n",
    "                if not dfs(st + 1, ed, node.left): return False\n",
    "                return True\n",
    "            else:\n",
    "                lval, rval = node.left.val, node.right.val\n",
    "                lidx, ridx = pos[lval], pos[rval]\n",
    "                if lidx < st or lidx > ed or ridx < st or ridx > ed: return False\n",
    "                if lidx == st + 1:\n",
    "                    if not dfs(st + 1, ridx - 1, node.left) or not dfs(ridx, ed, node.right): return False\n",
    "                    return True\n",
    "                elif ridx == st + 1:\n",
    "                    if not dfs(st + 1, lidx - 1, node.right) or not dfs(lidx, ed, node.left): return False\n",
    "                    ans.append(node.val)\n",
    "                    return True\n",
    "        res = dfs(0, len(voyage) - 1, root)\n",
    "        if not res: return [-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.index = 0\n",
    "        result = []\n",
    "\n",
    "        def dfs(root: TreeNode):\n",
    "            if not root:\n",
    "                return True\n",
    "            if root.val != voyage[self.index]:\n",
    "                return False\n",
    "            self.index += 1\n",
    "            if root.left and root.left.val != voyage[self.index]:\n",
    "                root.left, root.right = root.right, root.left\n",
    "                result.append(root.val)\n",
    "            return dfs(root.left) and dfs(root.right)\n",
    "        \n",
    "        if dfs(root):\n",
    "            return result\n",
    "        else:\n",
    "            return [-1]\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.flipped = []\n",
    "        self.idx = 0\n",
    "\n",
    "        def traverse(root):\n",
    "            if root:\n",
    "                if self.idx == len(voyage):\n",
    "                    return\n",
    "                if root.val != voyage[self.idx]:\n",
    "                    self.flipped = [-1]\n",
    "                    return\n",
    "\n",
    "                self.idx += 1\n",
    "                if root.left and root.left.val != voyage[self.idx]:\n",
    "                    self.flipped.append(root.val)\n",
    "                    traverse(root.right)\n",
    "                    traverse(root.left)\n",
    "                else:\n",
    "                    traverse(root.left)\n",
    "                    traverse(root.right)\n",
    "\n",
    "        traverse(root)\n",
    "        return [-1] if self.flipped and self.flipped[0] == -1 else self.flipped\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flip(self, root: Optional[TreeNode], voyage: List[int]):\n",
    "        if not root:\n",
    "            return [], voyage\n",
    "        if root.val != voyage[0]:\n",
    "            return [-1], voyage\n",
    "        if not root.left and not root.right:\n",
    "            return [], voyage[1:] if len(voyage)>1 else []\n",
    "        rs = []\n",
    "        if root.left and root.right:\n",
    "            print(root.val, root.right.val, root.left.val, voyage)\n",
    "        if root.left and root.right and root.right.val==voyage[1]:\n",
    "            print('00')\n",
    "            rs.append(root.val)\n",
    "            tmp = root.left\n",
    "            root.left = root.right\n",
    "            root.right = tmp\n",
    "        rs_left, voyage = self.flip(root.left, voyage[1:] if len(voyage)>1 else [])\n",
    "        print(rs, root.val, rs_left, voyage)\n",
    "        if -1 in rs_left:\n",
    "            return [-1], voyage\n",
    "        rs_right, voyage = self.flip(root.right, voyage)\n",
    "        if -1 in rs_right:\n",
    "            return [-1], voyage\n",
    "        return rs+rs_left+rs_right,  voyage\n",
    "\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        rs, _ = self.flip(root, voyage)\n",
    "        return rs\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        from collections import deque\n",
    "        s = deque()\n",
    "        if root.val != voyage[0]:\n",
    "            return [-1]\n",
    "        i=1\n",
    "        ans=list()\n",
    "        s.append(root)\n",
    "        while len(s) != 0:\n",
    "            temp = s.pop()\n",
    "            if temp.left is not None:\n",
    "                if temp.left.val != voyage[i]:\n",
    "                    swtemp = temp.left\n",
    "                    temp.left = temp.right\n",
    "                    temp.right = swtemp\n",
    "                    s.append(temp)\n",
    "                    if len(ans)!=0 and temp.val == ans[-1]:\n",
    "                        return [-1]\n",
    "                    ans.append(temp.val)\n",
    "                    continue\n",
    "                else:\n",
    "                    if temp.right is not None:\n",
    "                        i+=1\n",
    "                        s.extend([temp.right,temp.left])\n",
    "                    else:\n",
    "                        s.append(temp.left)\n",
    "                        i+=1    \n",
    "            elif temp.right is not None:\n",
    "                if temp.right.val != voyage[i]:\n",
    "                    return [-1]\n",
    "                else:\n",
    "                    s.append(temp.right)\n",
    "                    i+=1\n",
    "            else:\n",
    "                if len(s)!=0:\n",
    "                    temp = s.pop()\n",
    "                    if temp.val != voyage[i]:\n",
    "                        return [-1]\n",
    "                    else:\n",
    "                        s.append(temp)\n",
    "                        i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        # 这个翻转本质上就是先遍历左边还是右边\n",
    "        ans = []\n",
    "        n = len(voyage)\n",
    "        d = deque([root])\n",
    "        i = 0\n",
    "        while d:\n",
    "            cur = d.popleft()\n",
    "            if cur is None:\n",
    "                continue\n",
    "            if cur.val != voyage[i]:\n",
    "                return [-1]\n",
    "            if cur.left is None or cur.left.val != voyage[i + 1]:\n",
    "                if cur.right is not None and cur.left is not None:\n",
    "                    ans.append(cur.val)\n",
    "                d.appendleft(cur.left)\n",
    "                d.appendleft(cur.right)\n",
    "            else:\n",
    "                d.appendleft(cur.right)\n",
    "                d.appendleft(cur.left)\n",
    "            i += 1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        from collections import deque\n",
    "        s = deque()\n",
    "        length = len(voyage)\n",
    "        if root.val != voyage[0]:\n",
    "            return [-1]\n",
    "        i=1\n",
    "        flag = False\n",
    "        ans=list()\n",
    "        s.append(root)\n",
    "        while len(s) != 0:\n",
    "            print(ans)\n",
    "            temp = s.pop()\n",
    "            if temp.left is not None:\n",
    "                if temp.left.val != voyage[i]:\n",
    "                    swtemp = temp.left\n",
    "                    temp.left = temp.right\n",
    "                    temp.right = swtemp\n",
    "                    s.append(temp)\n",
    "                    if len(ans) !=0:\n",
    "                        if temp.val == ans[-1]:\n",
    "                            return [-1]\n",
    "                    ans.append(temp.val)\n",
    "                    continue\n",
    "                else:\n",
    "                    if temp.right is not None:\n",
    "                        i+=1\n",
    "                        s.extend([temp.right,temp.left])\n",
    "                    else:\n",
    "                        s.append(temp.left)\n",
    "                        i+=1    \n",
    "\n",
    "            elif temp.right is not None:\n",
    "                if temp.right.val != voyage[i]:\n",
    "                    return [-1]\n",
    "                else:\n",
    "                    s.append(temp.right)\n",
    "                    i+=1\n",
    "\n",
    "            else:\n",
    "                if len(s)!=0:\n",
    "                    temp = s.pop()\n",
    "                    if temp.val != voyage[i]:\n",
    "                        return [-1]\n",
    "                    else:\n",
    "                        s.append(temp)\n",
    "                        i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(node):\n",
    "            nonlocal i\n",
    "            if not node:\n",
    "                return True\n",
    "            if node.val != voyage[i]:\n",
    "                return False\n",
    "            i += 1\n",
    "            if dfs(node.left) and dfs(node.right):\n",
    "                return True\n",
    "            if dfs(node.right) and dfs(node.left):\n",
    "                ans.append(node.val)\n",
    "                return True\n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        if root.val != voyage[0]:\n",
    "            return [-1]\n",
    "        self.vals = []\n",
    "        self.index = 0\n",
    "        if not self.check(root, voyage):\n",
    "            return [-1]\n",
    "        return self.vals\n",
    "\n",
    "    def check(self, root, preorder):\n",
    "        if not root:\n",
    "            return True\n",
    "        if root.val != preorder[self.index]:\n",
    "            return False\n",
    "        self.index += 1\n",
    "        left_pre = self.check(root.left, preorder)\n",
    "        if not left_pre:\n",
    "            self.vals.append(root.val)\n",
    "            tmp = root.left\n",
    "            root.left = root.right\n",
    "            root.right = tmp\n",
    "            if not self.check(root.left, preorder):\n",
    "                return False\n",
    "        if not self.check(root.right, preorder):\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        def dfs(node, voyage):\n",
    "            nonlocal index, result\n",
    "            if node is None:\n",
    "                return True\n",
    "            if node.val != voyage[index]:\n",
    "                return False\n",
    "            \n",
    "            index += 1\n",
    "            if index < len(voyage) and node.left and node.left.val != voyage[index]:\n",
    "                result.append(node.val)\n",
    "                return dfs(node.right, voyage) and dfs(node.left, voyage)\n",
    "            return dfs(node.left, voyage) and dfs(node.right, voyage)\n",
    "        \n",
    "        result = []\n",
    "        index = 0\n",
    "        if dfs(root, voyage):\n",
    "            return result\n",
    "        return [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution(object):\n",
    "    def flipMatchVoyage(self, root, voyage):\n",
    "        self.flipped = []\n",
    "        self.i = 0\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.val != voyage[self.i]:\n",
    "                    self.flipped = [-1]\n",
    "                    return\n",
    "                self.i += 1\n",
    "\n",
    "                if (self.i < len(voyage) and\n",
    "                        node.left and node.left.val != voyage[self.i]):\n",
    "                    self.flipped.append(node.val)\n",
    "                    dfs(node.right)\n",
    "                    dfs(node.left)\n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "        if self.flipped and self.flipped[0] == -1:\n",
    "            self.flipped = [-1]\n",
    "        return self.flipped\n",
    "\n",
    "# 作者：LeetCode\n",
    "# 链接：https://leetcode.cn/problems/flip-binary-tree-to-match-preorder-traversal/solution/fan-zhuan-er-cha-shu-yi-pi-pei-xian-xu-bian-li-by-/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        idx = 0\n",
    "        res = []\n",
    "\n",
    "        def dfs(node):\n",
    "            nonlocal idx, res\n",
    "            if not node or res == [-1]:\n",
    "                return\n",
    "            if voyage[idx] != node.val:\n",
    "                res = [-1]\n",
    "                return\n",
    "            idx += 1\n",
    "            if node.left and node.left.val != voyage[idx]:\n",
    "                res.append(node.val)\n",
    "                dfs(node.right)\n",
    "                dfs(node.left)\n",
    "            else:\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = []\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        def traversal(root):\n",
    "            if(not root):\n",
    "                return True\n",
    "            self.path.append(root.val)\n",
    "            if(self.path == voyage[:len(self.path)]):\n",
    "                if(traversal(root.left) and traversal(root.right)):\n",
    "                    return True\n",
    "                if(traversal(root.right) and traversal(root.left)):\n",
    "                    result.append(root.val)\n",
    "                    return True\n",
    "            self.path.pop()\n",
    "            return False\n",
    "        if(traversal(root)):\n",
    "            return result\n",
    "        else:\n",
    "            return [-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        self.res = []\n",
    "\n",
    "        self.voyage = voyage\n",
    "        self.traverse(root)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root):\n",
    "        if root is None or -1 in self.res:\n",
    "            return \n",
    "\n",
    "        cur = self.voyage.pop(0)\n",
    "        if root.val != cur:\n",
    "            self.res = [-1]\n",
    "            return \n",
    "\n",
    "        if root.left and root.left.val != self.voyage[0]:\n",
    "            self.res.append(root.val)\n",
    "            self.traverse(root.right)\n",
    "            self.traverse(root.left)\n",
    "        else:\n",
    "            self.traverse(root.left)\n",
    "            self.traverse(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1\n",
    "                return ret\n",
    "            if root.val == voyage[i]:\n",
    "                i += 1\n",
    "                if root.left and root.right:\n",
    "                    if root.right.val == voyage[i]:\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                elif root.left:\n",
    "                    return dfs(root.left)\n",
    "                else:\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: TreeNode, voyage: List[int]) -> List[int]:\n",
    "        # 先序遍历时，若当前节点与对应的voyage数组中的元素值不相同，那么无法匹配，将res数组赋值为[-1]\n",
    "        # 若当前节点与对应的voyage数组中的元素值相同，那么检查当前节点的左节点，若左节点可以与voyage的下一个值匹配，则直接进入下一层遍历\n",
    "        # 若左节点与voyage的下一个值不匹配，那么交换左右节点，把即将交换的节点值压入最后要返回的res数组中，进入下一层遍历（也可直接把右节点传入先序遍历函数中进行遍历，省去一次交换的时间）\n",
    "        res = []\n",
    "        i = 0\n",
    "        def pre_order(root):\n",
    "            nonlocal res\n",
    "            nonlocal i\n",
    "            # 虽然本题一定存在root节点，但是还是需要在递归中判断root是否存在\n",
    "            # 因为需要将右侧子节点加入递归，右侧子节点可能为空\n",
    "            if root:\n",
    "                if root.val != voyage[i]:\n",
    "                    res = [-1]\n",
    "                    return\n",
    "                i += 1\n",
    "                if root.left and i < len(voyage) and root.left.val != voyage[i]:\n",
    "                    res.append(root.val)\n",
    "                    pre_order(root.right)\n",
    "                    pre_order(root.left)\n",
    "                else:\n",
    "                    pre_order(root.left)\n",
    "                    pre_order(root.right)\n",
    "            return\n",
    "        pre_order(root)\n",
    "        return [-1] if res and res[0] == -1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            # 若是樹葉（兩子皆空）\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1 # consume voyage[i]\n",
    "                return ret\n",
    "            # 若非樹葉\n",
    "            if root and root.val == voyage[i]:\n",
    "                i += 1 # consume voyage[i]\n",
    "                # 若兩子皆有\n",
    "                if root.left and root.right:\n",
    "                    # 若右子匹配 voyage[i]，則交換左右子\n",
    "                    if root.right.val == voyage[i]: # peek voyage[i]\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    # 遞歸求解左子與右子\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                # 若僅有左子\n",
    "                elif root.left:\n",
    "                    # 遞歸求解左子\n",
    "                    return dfs(root.left)\n",
    "                # 若僅有右子\n",
    "                else:\n",
    "                    # 遞歸求解右子\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def flipMatchVoyage(self, root: Optional[TreeNode], voyage: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        i = 0\n",
    "        def dfs(root,):\n",
    "            nonlocal ans, i\n",
    "            # 若是樹葉（沒有任何子）\n",
    "            if not root.left and not root.right:\n",
    "                ret = root.val == voyage[i]\n",
    "                i += 1 # consume voyage[i]\n",
    "                return ret\n",
    "            # 若非樹葉\n",
    "            if root.val == voyage[i]:\n",
    "                i += 1 # consume voyage[i]\n",
    "                # 若兩子皆有\n",
    "                if root.left and root.right:\n",
    "                    # 若右子匹配 voyage[i]，則交換左右子\n",
    "                    if root.right.val == voyage[i]: # peek voyage[i]\n",
    "                        root.left, root.right = root.right, root.left\n",
    "                        ans.append(root.val)\n",
    "                    # 遞歸求解左子與右子\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "                # 若僅有左子\n",
    "                elif root.left:\n",
    "                    # 遞歸求解左子\n",
    "                    return dfs(root.left)\n",
    "                # 若僅有右子\n",
    "                else:\n",
    "                    # 遞歸求解右子\n",
    "                    return dfs(root.right)\n",
    "\n",
    "                \n",
    "            return False\n",
    "        return ans if dfs(root) else [-1]\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
